// 版权所有2011 Go作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

// 包dsa实现FIPS 186-3中定义的数字签名算法。
// None
// 此包中的DSA操作不是使用恒定时间算法实现的。
// None
// 不推荐使用：DSA是一种传统的算法，现代的替代方法如
// 应改用Ed25519（由包crypto/Ed25519实现）。钥匙
// 对于1024位模（L1024N160参数），其加密能力较弱，而
// 较大的键没有得到广泛支持。请注意，FIPS 186-5不再批准
// 用于生成签名的DSA。
package dsa

import (
	"errors"
	"io"
	"math/big"

	"crypto/internal/randutil"
)

// 参数表示密钥的域参数。这些参数可以
// 可以跨多个键共享。Q的位长度必须是8的倍数。
type Parameters struct {
	P, Q, G *big.Int
}

// 公钥表示DSA公钥。
type PublicKey struct {
	Parameters
	Y *big.Int
}

// PrivateKey表示DSA私钥。
type PrivateKey struct {
	PublicKey
	X *big.Int
}

// 当此代码无法使用公钥时，会产生ErrInvalidPublicKey。
// FIPS对DSA密钥的格式要求非常严格，但其他代码可能会非常严格
// 少一点。因此，当使用可能由其他代码生成的密钥时，
// 必须处理此错误。
var ErrInvalidPublicKey = errors.New("crypto/dsa: invalid public key")

// ParameterSizes是素数的可接受位长度的枚举
// 在一组DSA参数中。见FIPS 186-3第4.2节。
type ParameterSizes int

const (
	L1024N160 ParameterSizes = iota
	L2048N224
	L2048N256
	L3072N256
)

// numMRTests是我们执行的Miller-Rabin素性测试的数量。我们
// 从FIPS 186-3的表C.1中选择最大建议数量。
const numMRTests = 64

// GenerateParameters将一组随机有效的DSA参数放入参数中。
// 即使在速度较快的机器上，此功能也可能需要几秒钟的时间。
func GenerateParameters(params *Parameters, rand io.Reader, sizes ParameterSizes) error {
	// 此函数不完全遵循FIPS 186-3，因为它不
	// 使用验证种子生成素数。验证
	// 种子似乎未被其他代码导出或使用
	// 省略它会使代码更干净。

	var L, N int
	switch sizes {
	case L1024N160:
		L = 1024
		N = 160
	case L2048N224:
		L = 2048
		N = 224
	case L2048N256:
		L = 2048
		N = 256
	case L3072N256:
		L = 3072
		N = 256
	default:
		return errors.New("crypto/dsa: invalid ParameterSizes")
	}

	qBytes := make([]byte, N/8)
	pBytes := make([]byte, L/8)

	q := new(big.Int)
	p := new(big.Int)
	rem := new(big.Int)
	one := new(big.Int)
	one.SetInt64(1)

GeneratePrimes:
	for {
		if _, err := io.ReadFull(rand, qBytes); err != nil {
			return err
		}

		qBytes[len(qBytes)-1] |= 1
		qBytes[0] |= 0x80
		q.SetBytes(qBytes)

		if !q.ProbablyPrime(numMRTests) {
			continue
		}

		for i := 0; i < 4*L; i++ {
			if _, err := io.ReadFull(rand, pBytes); err != nil {
				return err
			}

			pBytes[len(pBytes)-1] |= 1
			pBytes[0] |= 0x80

			p.SetBytes(pBytes)
			rem.Mod(p, q)
			rem.Sub(rem, one)
			p.Sub(p, rem)
			if p.BitLen() < L {
				continue
			}

			if !p.ProbablyPrime(numMRTests) {
				continue
			}

			params.P = p
			params.Q = q
			break GeneratePrimes
		}
	}

	h := new(big.Int)
	h.SetInt64(2)
	g := new(big.Int)

	pm1 := new(big.Int).Sub(p, one)
	e := new(big.Int).Div(pm1, q)

	for {
		g.Exp(h, e, p)
		if g.Cmp(one) == 0 {
			h.Add(h, one)
			continue
		}

		params.G = g
		return nil
	}
}

// GenerateKey生成公钥和私钥对。系统的参数
// PrivateKey必须已经有效（请参阅GenerateParameters）。
func GenerateKey(priv *PrivateKey, rand io.Reader) error {
	if priv.P == nil || priv.Q == nil || priv.G == nil {
		return errors.New("crypto/dsa: parameters not set up before generating key")
	}

	x := new(big.Int)
	xBytes := make([]byte, priv.Q.BitLen()/8)

	for {
		_, err := io.ReadFull(rand, xBytes)
		if err != nil {
			return err
		}
		x.SetBytes(xBytes)
		if x.Sign() != 0 && x.Cmp(priv.Q) < 0 {
			break
		}
	}

	priv.X = x
	priv.Y = new(big.Int)
	priv.Y.Exp(priv.G, x, priv.P)
	return nil
}

// 费马逆利用费马方法计算GF（P）中k的逆。
// 这比欧几里得方法（已实现）具有更好的恒定时间特性
// 在math/big.Int.ModInverse中）虽然math/big本身并不严格
// 恒定的时间，所以它不是完美的。
func fermatInverse(k, P *big.Int) *big.Int {
	two := big.NewInt(2)
	pMinus2 := new(big.Int).Sub(P, two)
	return new(big.Int).Exp(k, pMinus2, P)
}

// Sign对任意长度的哈希进行签名（这应该是对
// 更大的消息）使用私钥priv。它将签名作为
// 一对整数。私钥的安全性取决于密钥的熵
// 兰德。
// None
// 请注意，FIPS 186-3第4.6节规定应截断散列
// 到子组的字节长度。此函数不执行该操作
// 截断本身。
// None
// 请注意，带有攻击者控制的私钥的呼叫标志可能会
// 需要任意数量的CPU。
func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
	randutil.MaybeReadByte(rand)

	// FIPS 186-3，第4.6节

	n := priv.Q.BitLen()
	if priv.Q.Sign() <= 0 || priv.P.Sign() <= 0 || priv.G.Sign() <= 0 || priv.X.Sign() <= 0 || n%8 != 0 {
		err = ErrInvalidPublicKey
		return
	}
	n >>= 3

	var attempts int
	for attempts = 10; attempts > 0; attempts-- {
		k := new(big.Int)
		buf := make([]byte, n)
		for {
			_, err = io.ReadFull(rand, buf)
			if err != nil {
				return
			}
			k.SetBytes(buf)
			// priv.Q必须大于等于128，因为上面的测试
			// 要求它大于0，并且
			// ceil（log_2（Q））mod 8=0
			// 因此，这个循环将很快终止。
			if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
				break
			}
		}

		kInv := fermatInverse(k, priv.Q)

		r = new(big.Int).Exp(priv.G, k, priv.P)
		r.Mod(r, priv.Q)

		if r.Sign() == 0 {
			continue
		}

		z := k.SetBytes(hash)

		s = new(big.Int).Mul(priv.X, r)
		s.Add(s, z)
		s.Mod(s, priv.Q)
		s.Mul(s, kInv)
		s.Mod(s, priv.Q)

		if s.Sign() != 0 {
			break
		}
	}

	// 只有退化的私钥需要更多的密钥
	// 尝试。
	if attempts == 0 {
		return nil, nil, ErrInvalidPublicKey
	}

	return
}

// 验证使用公钥pub在散列的r，s中验证签名。信息技术
// 报告签名是否有效。
// None
// 请注意，FIPS 186-3第4.6节规定应截断散列
// 到子组的字节长度。此函数不执行该操作
// 截断本身。
func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
	// FIPS 186-3，第4.7节

	if pub.P.Sign() == 0 {
		return false
	}

	if r.Sign() < 1 || r.Cmp(pub.Q) >= 0 {
		return false
	}
	if s.Sign() < 1 || s.Cmp(pub.Q) >= 0 {
		return false
	}

	w := new(big.Int).ModInverse(s, pub.Q)
	if w == nil {
		return false
	}

	n := pub.Q.BitLen()
	if n%8 != 0 {
		return false
	}
	z := new(big.Int).SetBytes(hash)

	u1 := new(big.Int).Mul(z, w)
	u1.Mod(u1, pub.Q)
	u2 := w.Mul(r, w)
	u2.Mod(u2, pub.Q)
	v := u1.Exp(pub.G, u1, pub.P)
	u2.Exp(pub.Y, u2, pub.P)
	v.Mul(v, u2)
	v.Mod(v, pub.P)
	v.Mod(v, pub.Q)

	return v.Cmp(r) == 0
}
